/**
  * @file    :matrix_graph.hpp
  * @brief   :邻接矩阵图的模板类
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2023-12-30
*/

#ifndef GRAPH_MATRIX_GRAPH_H_
#define GRAPH_MATRIX_GRAPH_H_

#include "graph.hpp"
#include <algorithm>
#include <vector>


// 邻接举证图模板类实现
template<typename vertexType, typename weightType>
class MatrixGraph : public Graph<vertexType, weightType> {
private:
    weightType _maxWeight;             // 最大权值
    std::vector<vertexType> *_vertices;// 顶点集合
    weightType **_matrix;              // 邻接矩阵

public:
    // 构造函数(顶点数量上限/边权值上限/图类型)
    MatrixGraph(int type, int maxVertexCount, weightType maxWeight);

    // 构造函数（顶点数量上限/边权值上限/图类型/顶点结合/边集合）
    MatrixGraph(int type, int maxVertexCount, weightType maxWeight,
                const std::vector<vertexType> &vertices,
                const std::vector<Edge<vertexType, weightType>> &edges);

    // 析构函数
    ~MatrixGraph();

    // 获取顶点的索引
    virtual int getVertexIndex(const vertexType &vertex) const;

    // 通过索引获取顶点
    virtual bool getVertex(int index, vertexType &vertex) const;

    // 获取边权值
    virtual bool getEdgeWeight(const vertexType &start, const vertexType &end, weightType &weight) const;

    // 通过顶点索引获取权值
    virtual bool getEdgeWeightByIndex(int startIndex, int endIndex, weightType &weight) const;

    // 插入顶点
    virtual bool insertVertex(const vertexType &vertex);

    // 插入边
    virtual bool insertEdge(const vertexType &start, const vertexType &end, const weightType &weight);

    // 删除顶点
    virtual bool removeVertex(const vertexType &vertex);

    // 删除边
    virtual bool removeEdge(const vertexType &start, const vertexType &end);
};

// 构造函数(顶点数量上限/边权值上限/图类型)
template<typename vertexType, typename weightType>
MatrixGraph<vertexType, weightType>::MatrixGraph(int type, int maxVertexCount, weightType maxWeight) {
    // 非法性检测
    if (type != Graph<vertexType, weightType>::UNDIRECTED &&
        type != Graph<vertexType, weightType>::DIRECTED) {
        throw std::invalid_argument("类型异常");
    }

    this->_type = type;
    this->_vertexCount = 0;
    this->_edgeCount = 0;
    this->_maxVertexCount = maxVertexCount;
    this->_maxWeight = maxWeight;

    // 根据不同类型分配不同空间
    if (type == Graph<vertexType, weightType>::UNDIRECTED) {
        this->_degree = new std::vector<int>(this->_maxVertexCount, -1);
        if (!this->_degree) {
            throw std::bad_alloc();
        }

        this->_outDegree = nullptr;
        this->_inDegree = nullptr;
    } else if (type == Graph<vertexType, weightType>::DIRECTED) {
        this->_degree = nullptr;

        this->_outDegree = new std::vector<int>(this->_maxVertexCount, -1);
        if (!this->_outDegree) {
            throw std::bad_alloc();
        }

        this->_inDegree = new std::vector<int>(this->_maxVertexCount, -1);
        if (!this->_inDegree) {
            throw std::bad_alloc();
        }
    }

    // 分配邻接矩阵空间
    this->_matrix = new weightType *[this->_maxVertexCount];
    for (int row = 0; row < this->_maxVertexCount; row++) {
        this->_matrix[row] = new weightType[this->_maxVertexCount];
        if (!this->_matrix[row]) {
            throw std::bad_alloc();
        }

        for (int col = 0; col < this->_maxVertexCount; col++) {
            this->_matrix[row][col] = maxWeight;
        }
    }

    // 分配顶点集合空间
    this->_vertices = new std::vector<vertexType>(this->_maxVertexCount, vertexType());
    if (!this->_vertices) {
        throw std::bad_alloc();
    }
}

// 构造函数（顶点数量上限/边权值上限/图类型/顶点结合/边集合）
template<typename vertexType, typename weightType>
MatrixGraph<vertexType, weightType>::MatrixGraph(int type, int maxVertexCount, weightType maxWeight,
                                                 const std::vector<vertexType> &vertices,
                                                 const std::vector<Edge<vertexType, weightType>> &edges) {

    // 非法性检测
    if (type != Graph<vertexType, weightType>::UNDIRECTED &&
        type != Graph<vertexType, weightType>::DIRECTED) {
        throw std::invalid_argument("类型异常");
    }

    this->_type = type;
    this->_vertexCount = vertices.size();
    this->_edgeCount = edges.size();
    this->_maxVertexCount = maxVertexCount;
    this->_maxWeight = maxWeight;

    this->_vertices = new std::vector<vertexType>(vertices);

    // 分配邻接举证空间
    this->_matrix = new weightType *[this->_maxVertexCount];
    if (!this->_matrix) {
        throw std::bad_alloc();
    }

    for (int row = 0; row < this->_maxVertexCount; row++) {
        this->_matrix[row] = new weightType[this->_maxVertexCount];
        if (!this->_matrix[row]) {
            throw std::bad_alloc();
        }

        for (int col = 0; col < this->_maxVertexCount; col++) {
            this->_matrix[row][col] = maxWeight;
        }
    }

    // 分别处理无向图和有向图
    if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
        this->_degree = new std::vector<int>(this->_maxVertexCount, -1);
        this->_outDegree = nullptr;
        this->_inDegree = nullptr;

        // 计算顶点的度
        for (auto it = edges.begin(); it != edges.end(); it++) {
            int startIndex, endIndex;

            // 初始化顶点的度
            auto curStart = std::find(vertices.begin(), vertices.end(), it->_start);
            if (curStart != vertices.end()) {
                startIndex = std::distance(vertices.begin(), curStart);
                (*this->_degree)[startIndex]++;
            }

            auto curEnd = std::find(vertices.begin(), vertices.end(), it->_end);
            if (curEnd != vertices.end()) {
                endIndex = std::distance(vertices.begin(), curEnd);
                (*(this->_degree))[endIndex]++;
            }

            this->_matrix[startIndex][endIndex] = it->_weight;
        }
    } else if (this->_type == Graph<vertexType, weightType>::DIRECTED) {

        this->_degree = nullptr;
        this->_outDegree = new std::vector<int>(this->_maxVertexCount, -1);
        this->_inDegree = new std::vector<int>(this->_maxVertexCount, -1);

        for (auto it = edges.begin(); it != edges.end(); it++) {
            auto curOut = std::find(vertices.begin(), vertices.end(), it->_start);
            auto curIn = std::find(vertices.begin(), vertices.end(), it->_end);

            if (curOut != vertices.end() && curIn != vertices.end()) {
                int outIndex = std::distance(vertices.begin(), curOut);
                int inIndex = std::distance(vertices.begin(), curIn);
                (*(this->_inDegree))[inIndex]++;
                (*(this->_outDegree))[outIndex]++;

                this->_matrix[outIndex][inIndex] = it->_weight;
            }
        }
    }
}

// 析构函数
template<typename vertexType, typename weightType>
MatrixGraph<vertexType, weightType>::~MatrixGraph() {
    delete this->_vertices;
    for (int row = 0; row < this->_maxVertexCount; row++) {
        delete this->_matrix[row];
    }
    delete this->_matrix;

    if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
        delete this->_degree;
    } else {
        delete this->_inDegree;
        delete this->_outDegree;
    }
}

// 获取顶点的索引
template<typename vertexType, typename weightType>
int MatrixGraph<vertexType, weightType>::getVertexIndex(const vertexType &vertex) const {
    auto it = std::find(_vertices->begin(), _vertices->end(), vertex);
    if (it == _vertices->end()) {
        return -1;
    }
    return std::distance(_vertices->begin(), it);
}

// 通过索引获取顶点
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::getVertex(int index, vertexType &vertex) const {
    // 非法处理
    if (index < 0 || index >= this->_vertexCount) {
        return false;
    }

    vertex = (*_vertices)[index];

    return true;
}

// 获取边权值
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::getEdgeWeight(const vertexType &start,
                                                        const vertexType &end,
                                                        weightType &weight) const {
    int startIndex = getVertexIndex(start);
    int endIndex = getVertexIndex(end);

    return getEdgeWeightByIndex(startIndex, endIndex, weight);
}

// 通过顶点索引获取权值
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::getEdgeWeightByIndex(int startIndex,
                                                               int endIndex,
                                                               weightType &weight) const {
    // 非法性检测
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount) {
        return false;
    }

    weight = _matrix[startIndex][endIndex];

    return true;
}

// 插入顶点
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::insertVertex(const vertexType &vertex) {
    // 容量不足
    if (this->_vertexCount >= this->_maxVertexCount) {
        return false;
    }

    // 已经存在相同顶点
    if (getVertexIndex(vertex) != -1) {
        return false;
    }

    _vertices->push_back(vertex);// 顶点集合中插入该顶点
    this->_vertexCount++;        // 顶点数量自增

    // 分别处理有向图和无向图
    int index = getVertexIndex(vertex);
    if (this->_type == Graph<vertexType, weightType>::DIRECTED) {
        (*this->_degree)[index] = 0;
    } else {
        (*this->_outDegree)[index] = 0;
        (*this->_inDegree)[index] = 0;
    }

    return true;
}

// 插入边
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::insertEdge(const vertexType &start,
                                                     const vertexType &end,
                                                     const weightType &weight) {
    int startIndex = getVertexIndex(start);
    int endIndex = getVertexIndex(end);

    // 非法处理
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount ||
        startIndex == endIndex ||
        weight >= _maxWeight) {
        return false;
    }

    this->_edgeCount++;                    // 边数量自增
    _matrix[startIndex][endIndex] = weight;// 邻接矩阵赋值

    // 分别处理有向图和无向图
    if (this->_type == Graph<vertexType, weightType>::DIRECTED) {
        (*this->_inDegree)[endIndex]++;
        (*this->_outDegree)[startIndex]++;
    } else {
        (*this->_degree)[startIndex]++;
        (*this->_degree)[endIndex]++;
    }

    return true;
}

// 删除顶点
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::removeVertex(const vertexType &vertex) {
    int targetIndex = getVertexIndex(vertex);

    // 非法性检测
    if (targetIndex < 0 || targetIndex >= this->_vertexCount) {
        return false;
    }

    // 分别处理有向图和无向图
    if (this->_type == Graph<vertexType, weightType>::DIRECTED) {
        for (int endIndex = 0; endIndex < this->_vertexCount; endIndex++) {
            if (_matrix[targetIndex][endIndex] != _maxWeight) {
                (*this->_inDegree)[endIndex]--;             // 修改入度集合
                _matrix[targetIndex][endIndex] = _maxWeight;// 删除与该顶点关联的边
                this->_edgeCount--;
            }

            if (_matrix[endIndex][targetIndex] != _maxWeight) {
                (*this->_outDegree)[endIndex]--;            // 修改出度集合
                _matrix[endIndex][targetIndex] = _maxWeight;// 删除与该顶点关联的边
                this->_edgeCount--;
            }
        }
        // 删除该顶点的入度和出度
        this->_inDegree->erase(this->_inDegree->begin() + targetIndex);
        this->_outDegree->erase(this->_outDegree->begin() + targetIndex);
    } else {
        for (int endIndex = 0; endIndex < this->_vertexCount; endIndex++) {
            if (_matrix[targetIndex][endIndex] != _maxWeight) {
                (*this->_degree)[endIndex]--;               // 修改度集合
                _matrix[targetIndex][endIndex] = _maxWeight;// 删除与该顶点关联的边
                this->_edgeCount--;
            }

            if (_matrix[endIndex][targetIndex] != _maxWeight) {
                (*this->_degree)[endIndex]--;               // 修改度集合
                _matrix[endIndex][targetIndex] = _maxWeight;// 删除与该顶点关联的边
                this->_edgeCount--;
            }
        }
        this->_degree->erase(this->_degree->begin() + targetIndex);// 删除该顶点的度
    }

    // 修改邻接矩阵
    for (int row = targetIndex + 1; row < this->_vertexCount; row++) {
        for (int col = 0; col < this->_vertexCount; col++) {
            _matrix[row - 1][col] = _matrix[row][col];
        }
    }
    for (int col = targetIndex + 1; col < this->_vertexCount; col++) {
        for (int row = 0; row < this->_vertexCount; row++) {
            _matrix[row][col - 1] = _matrix[row][col];
        }
    }

    _vertices->erase(_vertices->begin() + targetIndex);// 删除顶点集合中的顶点
    this->_vertexCount--;                              // 顶点数量自减

    return true;
}

// 删除边
template<typename vertexType, typename weightType>
bool MatrixGraph<vertexType, weightType>::removeEdge(const vertexType &start, const vertexType &end) {
    int startIndex = getVertexIndex(start);
    int endIndex = getVertexIndex(end);

    // 非法性检测
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount ||
        startIndex == endIndex) {
        return false;
    }

    // 分别处理有向图和无向图
    if (this->_type == Graph<vertexType, weightType>::DIRECTED) {
        (*this->_outDegree)[startIndex]--;
        (*this->_inDegree)[endIndex]--;
    } else {
        (*this->_degree)[startIndex]--;
        (*this->_degree)[endIndex]--;
    }

    this->_edgeCount--;

    return true;
}

// 重载 << 运算符
template<typename vertexType, typename weightType>
std::ostream &operator<<(std::ostream &out, MatrixGraph<vertexType, weightType> &graph) {

    // ---------- 1 打印图的各种信息 ----------
    out << "# 基本信息 #" << std::endl;

    // 1.1 打印结点信息
    out << "边数量：" << graph.getEdgeCount() << std::endl;
    out << "结点数量: " << graph.getVertexCount() << std::endl;
    for (int i = 0; i < graph.getVertexCount(); i++) {
        vertexType vertex;
        graph.getVertex(i, vertex);
        out << vertex << " ";
    }
    std::cout << std::endl;

    // ---------- 2 打印邻接矩阵信息 ----------
    out << "# 邻接矩阵信息 #" << std::endl;
    for (int row = 0; row < graph.getVertexCount(); row++) {
        for (int col = 0; col < graph.getVertexCount(); col++) {

            weightType weight;
            bool res = graph.getEdgeWeightByIndex(row, col, weight);
            if (!res) {
                continue;
            }

            out << "[" << row << "][" << col << "]: " << weight << std::endl;
        }
    }

    return out;
}

#endif// GRAPH_MATRIX_GRAPH_H_